import java.util.Arrays;
import java.util.Comparator;

/**
 * 452. 用最少数量的箭引爆气球
 * https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
 */
public class Solutions_452 {
    public static void main(String[] args) {
//        int[][] points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};  // output: 2
//        int[][] points = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};  // output: 4
//        int[][] points = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};  // output: 2
//        int[][] points = {{1, 2}};  // output: 1
//        int[][] points = {{2, 3}, {2, 3}};  // output: 1
        int[][] points = {{-2147483646, -2147483645}, {2147483646, 2147483647}};  // output: 2

        int result = findMinArrowShots(points);
        System.out.println(result);
    }

    public static int findMinArrowShots(int[][] points) {
        if (points == null || points.length < 1) {
            return 0;
        }
        // 排序规则：按照结束坐标升序排列
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 存在极端用例时，用 o1[1] - o2[1] 会溢出，导致排序混乱
                return Integer.compare(o1[1], o2[1]);
            }
        });
        // 结束坐标是固定的，无法扩充
        int end = points[0][1];
        int res = 1;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                // 说明该气球不在 end 以内，需要重新定义一个区间，并以 points[i][1] 作为结束坐标
                res ++;
                end = points[i][1];
            }
        }
        return res;
    }
}
